#include "bst_tree.h"
#include <iostream>

using std::cout;
using std::endl;

void test1()
{
    BST<int> tree;

    int arr[] = {58, 24, 67, 0, 34, 62, 69, 5, 41, 64, 78};
    int len = sizeof(arr) / sizeof(int);

    for (int i{}; i < len; i++)
    {
        tree.recursion_insert(arr[i]);
    }
    tree.recursion_insert(0);

    cout << std::boolalpha;
    cout << tree.contain(0) << endl;
    cout << tree.contain(-1) << endl;
    cout << tree.high() << endl;
    cout << tree.num() << endl;
    // tree.levelOrder();
    tree.foreach ();
    cout << tree.recursion_contain(0) << endl;
    cout << tree.recursion_contain(-1) << endl;
    // tree.recursion_erase(5);
    // tree.foreach();
    tree.recursion_erase(-1);
    tree.foreach ();
    tree.preForeach();
    tree.inForeach();
    tree.levelForeach();
    tree.lastForeach();

    vector<int> vec;
    tree.queryElems(vec, 10, 70);
    for (int i : vec)
    {
        cout << i << " ";
    }
    cout << endl;
    cout << tree.isBST() << endl;
    BST<int> child;
    child.insert(58);
    child.recursion_insert(67);
    child.recursion_insert(69);
    child.recursion_insert(78);
    child.recursion_insert(79);
    cout << tree.isChild(child) << endl;

    cout << tree.lastestParent(5, 24)->val_ << endl;
    cout << tree.getLCA(5, 41) << endl;

    tree.mirror();
    tree.inForeach();

    cout << tree.isSymmetry() << endl;
}

void test2()
{
    BST<int> tree;
    tree.root_ = new BST<int>::Node(40);
    tree.root_->left_ = new BST<int>::Node(20);
    tree.root_->right_ = new BST<int>::Node(20);

    tree.root_->left_->left_ = new BST<int>::Node(10);
    tree.root_->right_->right_ = new BST<int>::Node(10);

    tree.root_->left_->right_ = new BST<int>::Node(15);
    tree.root_->right_->left_ = new BST<int>::Node(15);


    tree.root_->left_->left_->right_ = new BST<int>::Node(12);
    tree.root_->right_->right_->left_ = new BST<int>::Node(12);

    cout << std::boolalpha;
    cout << tree.isSymmetry() << endl;
    tree.inForeach();
}

void test3()
{
    // V L R -> R L V
    int pre[] = {58, 24, 0, 5, 34, 41, 67, 62, 64, 69, 78};
    int in[] = {0, 5, 24, 34, 41, 58, 62, 64, 67, 69, 78};
    BST<int> tree;
    tree.rebuild(pre, 0, 10, in, 0, 10);
    tree.preForeach();
    tree.inForeach();
    cout << tree.isBalance() << endl;
    tree.insert(12);
    cout << tree.isBalance() << endl;

    cout << tree.getKVal(9)->val_ << endl;
    tree.lastForeach();
    cout << tree.preGetV(9)->val_ << endl;
}

int main(int args, char *argv[])
{
    // test1();
    // test2();
    test3();
    return 0;
}